/**
 * 动态规划-斐波拉契数-力扣126
 */

public class Practice_11 {
    public static void main(String[] args) {
        int n = 48;
        int result = fib(n);
        System.out.println(result);
    }
    public static int fib(int n) {
        final int MOD = 1000000007;
        if (n <= 1) {
            return n;
        }
        if (n < 0) {
            return -1;
        }

        int[] Dp = new int[n + 1];
        Dp[0] = 0;
        Dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            Dp[i] = (Dp[i - 1] + Dp[i - 2])%MOD;
        }
        return Dp[n];
    }

}
